Given a connected undirected graph, tell if its
minimum spanning tree is unique.
Definition 1 (Spanning Tree): Consider a connected, undirected
graph G = (V, E). A spanning tree of G is a subgraph of G, say T = (V', E'),
with the following properties:
1. V' = V.
2. T is connected and acyclic.
Definition 2 (Minimum Spanning Tree): Consider an edge-weighted,
connected, undirected graph G = (V, E). The minimum spanning tree T = (V, E')
of G is the spanning tree that has the smallest total cost. The total cost of T
means the sum of the weights on all the edges in E'.
Input. The first line contains a single integer t (1 ≤ t ≤ 20), the number of test cases.
Each case represents a graph. It begins with a line containing two integers n and m (1 ≤ n ≤
100), the number of nodes and edges. Each of the following m lines contains a
triple (xi, yi, wi), indicating that xi
and yi are connected by an
edge with weight = wi. For
any two nodes, there is at most one edge connecting them.
Output. For each input, if the MST is unique, print the total
cost of it, or otherwise print the string 'Not Unique!'.
Sample Input
2
3 3
1 2 1
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2
Sample
Output
3
Not Unique!
ãðàôû – ìèíèìàëüíîå îñòîâíîå äåðåâî
Ìèíèìàëüíîå îñòîâíîå äåðåâî
(MST) íå óíèêàëüíî, åñëè âåëè÷èíà ïåðâîãî MST ðàâíî âåëè÷èíå âòîðîãî MST. Äëÿ
íàõîæäåíèÿ ïåðâîãî è âòîðîãî MST âîñïîëüçóåìñÿ àëãîðèòìîì Êðóñêàëà,
áàçèðóþùåãîñÿ íà ñèñòåìå íåïåðåñåêàþùèõñÿ ìíîæåñòâ.
Ðåàëèçàöèÿ àëãîðèòìà
#include <cstdio>
#include <vector>
#include <algorithm>
#define MAXV 110
using namespace
std;
struct Edge
{
int u, v, dist;
Edge(int u = 0, int v = 0,
int dist = 0) : u(u), v(v), dist(dist) {}
};
Edge temp;
vector<Edge> e;
vector<int> MSTEdges;
int mas[MAXV], size[MAXV], res, res1;
void swap(int
&x, int &y)
{
int t = x; x = y; y = t;
}
int Repr(int
n)
{
if (n == mas[n]) return
n;
return mas[n] = Repr(mas[n]);
}
int Union(int
x,int y)
{
x = Repr(x); y =
Repr(y);
if(x == y) return 0;
if (size[x] < size[y]) swap(x,y);
mas[y] = x;
size[x] += size[y];
return 1;
}
int lt(Edge a, Edge b)
{
return (a.dist < b.dist);
}
int i, j, n, m, tests;
int cnt, flag;
int main(void)
{
scanf("%d",&tests);
while(tests--)
{
scanf("%d %d",&n,&m);
for(i = 1; i <= n; i++) mas[i] = i, size[i] = 1;
e.clear();
MSTEdges.clear();
for(i = 0; i < m; i++)
{
scanf("%d %d %d",&temp.u,&temp.v,&temp.dist);
e.push_back(temp);
}
sort(e.begin(),e.end(),lt);
res = 0;
for(i = 0; i < m; i++)
if (Union(e[i].u,e[i].v))
{
res +=
e[i].dist;
MSTEdges.push_back(i);
}
for(flag = i = 0; i < MSTEdges.size(); i++)
{
res1 = 0;
cnt = 1;
for(j = 1; j <= n; j++) mas[j] = j, size[j] = 1;
for(j = 0; j < m; j++)
{
if (j == MSTEdges[i]) continue;
if (Union(e[j].u,e[j].v))
{
res1 +=
e[j].dist;
cnt++;
}
}
if ((cnt == n) && (res1 == res))
{
flag = 1;
break;
}
}
if (flag) printf("Not
Unique!\n");
else printf("%d\n",res);
}
return 0;
}